The task of creating an efficient schedule for a collection of personnel is known to be a very complex constraint satisfaction problem. The problem becomes even more complex when the number of personnel is large, or when there are variable constraints upon the shifts such as the number of breaks within an person's shift, the scheduling of the breaks within a shift, and the lengths of the breaks.
Traditionally, scheduling is performed manually. Because the manual preparation of schedules is very laborious, however, computerized scheduling methods have been devised to perform the task of scheduling. Although computerized scheduling is far faster than manual scheduling, it often does not produce schedules that make the most efficient use of personnel. One major reason for the difficulty in producing efficient schedules is that the scheduling problem is a computational problem of type NP-complete, i.e. the only known algorithms to solve the problem require an amount of time that grows exponentially with the size of the problem. There are no known algorithms, therefore, which can perfectly solve the scheduling problem in less than exponential time. The problem of generating a good schedule, therefore, requires computational techniques for maximizing the schedule's efficiency while minimizing the amount of computational time, and inherently involves trade-offs that are peculiar to each specific application.
Traditional resource scheduling software packages include little or no mechanisms for the user to specify customized rules of a highly expressive nature. Instead, the user must simply follow a strict workflow imposed by the software or the user must specify constraints in great detail, requiring for example specifications of every particular personnel and every particular case of the rule individually.
Microsoft Outlook™ and other software products include simple interfaces for creating meaningful sentences using drag-and-drop actions. The structure of the “sentences” is not dynamically based on inputs by the user in general. They are fixed branches of possible values and sets of values. A real-time database lookup feature is not part of these systems.
U.S. Pat. No. 5,909,678 teaches building statements by dragging and dropping templates and components, and is specific to a system with selectable objects (for the “blanks”) only.
U.S. Pat. No. 5,682,542 is very specific to construction of statements containing noun and verb objects only.
U.S. Pat. Nos. 5,590,322 and 5,592,668 teach designing queries for an information system, including a drag-and-drop method for creating the queries, but include only a system that maps the query to a specific internal structure (the fact tree representation).U.S. Pat. No. 5,584,024 teaches a narrow database query system. However, the system includes a user interface allowing a user to select from tables to create queries that are guaranteed to be syntactically and semantically correct, and thus conform to a strict grammar.U.S. Pat. No. 4,829,423 generally teaches any interface for users to create sentences from a specified grammar, including a means for generating all possible choices midway through the process based on user inputs thus far.U.S. Pat. No. 5,802,255 teaches a user interface design that enables building rules in the area of intelligent interaction with rules. However, the rules taught are specifically condition-action rules and are thus highly structured.U.S. Pat. No. 5,596,502 is a narrow manufacturing application. U.S. Pat. No. 5,444,632 describes factory lot processing and scheduling methods.